package bintree.leetcode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * @Author: yuisama
 * @Date: 2022/9/22 11:11
 * @Description:
 */
public class Num515_LargestValues {
    List<Integer> res = new ArrayList<>();
    // DFS递归实现
    public List<Integer> largestValues(TreeNode root) {
        if (root == null) {
            return res;
        }
        traverse(root,0);
        return res;
    }
    private void traverse(TreeNode root, int depth) {
        // base case
        if (root == null) {
            return;
        }
        // 前序位置
        if (res.size() <= depth) {
            // 第一次进入该层
            res.add(root.val);
        }else {
            // 当前行的最大值
            res.set(depth,Math.max(res.get(depth),root.val));
        }
        traverse(root.left,depth + 1);
        traverse(root.right,depth + 1);
    }
//    public List<Integer> largestValues(TreeNode root) {
//        if (root == null) {
//            return res;
//        }
//        List<TreeNode> curList = new ArrayList<>();
//        curList.add(root);
//        traverse(curList);
//        return res;
//    }
//    public void traverse(List<TreeNode> curList) {
//        // base case，当前层为空，遍历结束
//        if (curList.isEmpty()) {
//            return;
//        }
//        // 前序位置，处理当前层的所有节点，将最大值保存在res中
//        // 将下一层节点存在nextList中
//        List<TreeNode> nextList = new ArrayList<>();
//        int max = Integer.MIN_VALUE;
//        for (TreeNode node : curList) {
//            max = Math.max(max,node.val);
//            if (node.left != null) {
//                nextList.add(node.left);
//            }
//            if (node.right != null) {
//                nextList.add(node.right);
//            }
//        }
//        res.add(max);
//        traverse(nextList);
//    }
    // BFS常规迭代思路的找每一层最大值
//    public List<Integer> largestValues(TreeNode root) {
//        List<Integer> ret = new ArrayList<>();
//        if (root == null) {
//            return ret;
//        }
//        Queue<TreeNode> queue = new ArrayDeque<>();
//        queue.offer(root);
//        while (!queue.isEmpty()) {
//            int size = queue.size();
//            int max = Integer.MIN_VALUE;
//            for (int i = 0; i < size; i++) {
//                TreeNode node = queue.poll();
//                max = Math.max(max,node.val);
//                if (node.left != null) {
//                    queue.offer(node.left);
//                }
//                if (node.right != null) {
//                    queue.offer(node.right);
//                }
//            }
//            ret.add(max);
//        }
//        return ret;
//    }
}
